package 算法题汇总;

import java.util.ArrayList;
import java.util.HashMap;

public class LRU {

        static class Node{
            int key,value;
            Node pre,next;
            Node(int k,int v){
                this.key = k;
                this.value = v;
            }
        }
        Node head = new Node(0,0);
        Node tail = new Node(0,0);//建立两个双向链表的头节点

        private void add(Node node){
            head.next.pre = node;
            node.next = head.next;
            head.next = node;
            node.pre = head;
        }
        private void remove(Node node){
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }

        public int[] LRU (int[][] operators, int k) {
            int count = 0;//记录添加了多少个
            ArrayList<Integer> list = new ArrayList<>();
            HashMap<Integer,Node> map = new HashMap<>();
            head.next = tail;
            tail.pre = head;
            for (int i = 0; i < operators.length; i++) {
                if(operators[i][0] == 1){
                    Node node = map.get(operators[i][1]);
                    if(node == null){
                        Node temp = new Node(operators[i][1],operators[i][2]);
                        map.put(operators[i][1],temp);
                        add(temp);
                        count++;
                    }else{
                        node.value = operators[i][2];
                        remove(node);
                        add(node);
                    }
                    if(count > k){
                        Node delete = tail.pre;
                        map.remove(delete.key);
                        remove(delete);
                        count--;
                    }
                }
                if(operators[i][0] == 2){
                    Node node = map.get(operators[i][1]);
                    if(node == null){
                        list.add(-1);
                    }else{
                        list.add(node.value);
                        remove(node);
                        add(node);
                    }
                }
            }
            Integer[] result=list.toArray(new Integer[list.size()]);
            int[] res=new int[result.length];
            for(int i=0;i<result.length;i++){
                res[i]=result[i];
            }
            return res;
        }

}
